package com.华为OD.牛客;

import java.util.Arrays;
import java.util.Scanner;

public class HJ16购物单 {
    static class Good{
        public Good(int v,int p,int ma){
            this.v=v;
            this.p=p;
            this.ma=ma;
        }
        public int v,p,ma;
        public boolean hasBuy=false;
    }
    public static Good[]goods;
    //进入递归的顺序
    public static Good[]order;
    public static int dp(int i,int N){
        if(i<0)
            return 0;
        Good g=order[i];
        if(g.v>N||(g.ma!=-1&&!goods[g.ma].hasBuy)){
            return dp(i-1,N);
        }
        g.hasBuy=true;
        int ifBuy=dp(i-1,N-g.v)+g.p*g.v;
        g.hasBuy=false;
        int notBuy=dp(i-1,N);
        return Math.max(ifBuy,notBuy);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int m = in.nextInt();
        goods = new Good[m];
        order = new Good[m];
        int i=0;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            goods[i++]=new Good(in.nextInt(),in.nextInt(),in.nextInt()-1);
        }
        //安排进入递归的顺序，保证主件先选
        i=0;
        int j=m-1;
        for(int k=0;k<m;k++){
            Good g=goods[k];
            if(g.ma==-1)
                order[j--]=g;
            else
                order[i++]=g;
        }
        System.out.print(dp(m-1,N));
    }
}
